package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;
import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_938_二叉搜索树的范围和 {
    @Test
    public void main() {
        
        Solution solution = new 力扣_938_二叉搜索树的范围和().new Solution();
        System.out.println(solution);
    }

    /**
     题目：给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
     示例 1：
     输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
     输出：32

     示例 2：
     输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
     输出：23

     分析：【P 💖】
        1.dfs递归:子树相加
            --执行耗时:0 ms,击败了100.00% 的Java用户
            --编码耗时:[6:57]

     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
//    Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        if(root==null)
            return sum;
        if(root.val>low)
            sum+=rangeSumBST(root.left,low,high);
        if(root.val<high)
            sum+=rangeSumBST(root.right,low,high);
        if(root.val>=low && root.val<=high)
            sum+=root.val;
        return sum;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}